⟸ Go Back ⟸
Exercise 9 (Homework 3).
(theory of languages, Arden's Lemma, hard exercise, regular expressions)

Arden’s Lemma and applications

  1. Arden’s Lemma. Given languages A,B\subseteq \Sigma^* and the equation X=AX\cup B, \tag{1}

    show that

    1. X=A^*B is a solution of (Equation 1), that is A^*B=AA^*B\cup B;
    2. if L is a solution of (Equation 1) then L\supseteq A^*B;
    3. if \lambda\notin A then A^*B is the unique solution of (Equation 1).

  2. Symmetric version of Arden’s Lemma. Given A,B\subseteq \Sigma^* and the equation Y=YA\cup B, \tag{2}

    show that

    1. Y=BA^* is a solution of (Equation 2);
    2. if L is a solution of (Equation 2) then L\supseteq BA^*;
    3. if \lambda\notin A then BA^* is the unique solution of (Equation 2).

  3. For each of the following languages L, give a DFA A_L recognizing L and two regular expressions representing L. Obtain the regular expressions using Arden’s lemma and the symmetric version of Arden’s lemma on A_L where

    1. L is the language of words on \{a,b\} with an even number of as;
    2. L is the language of words on \{a,b\} with either an even number of as or an even number of bs;
    3. L is the language of words on \{a,b\} ending with ababa;
    4. L is the language of words on \{a,b\} not containing the subword aba;
    5. L is the language of words on \{a,b,c\} such that between every two as there is at least one b;
    6. L is the language of words on \{0,1\} with at least two consecutive 0s;
    7. L=\overline{\{w\in \{0,1\}^*\mid \mathtt{value}_2(w)\in 3\mathbb N\}}.
    Tip

    Given a DFA A, we can associate to each of its states q two variables: \begin{aligned} X_q&=\text{the language of the words that in $A$ bring us from $q$ to an accepting state} \\ Y_q&=\text{the language of the words that in $A$ bring us from the initial state to $q$} \end{aligned} Using the variables above, we can then set-up two systems of equations and solve them using Arden’s lemma (and its symmetric version). The system that uses the variables X_q can be resolved using Arden’s lemma, while the one using Y_q can be solved using the symmetric version of Arden’s lemma.